package com.acwing.partition11;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class AC1013机器分配 {

    private static int profit = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split("\\s+");
            for (int j = 0; j < m; j++) matrix[i][j] = Integer.parseInt(s[j]);
        }
        int[] answer = dynamicProgramming(matrix);
        writer.write(profit + "\n");
        for (int i = 1; i < answer.length; i++) writer.write(i + " " + answer[i] + "\n");
        writer.flush();
    }

    private static int[] dynamicProgramming(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            int[] company = matrix[i - 1];
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                //枚举每个组中的物品
                for (int k = 1; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + company[k - 1]);
                }
            }
        }
        profit = dp[n][m];
        //回溯寻找具体方案数
        int[] answer = new int[n + 1];
        int j = m;
        //j的体积是从大到小的，为了和状态转移表示的一致，所以遍历物品也需要反序遍历
        for (int i = n; i >= 1; i--) {
            int[] company = matrix[i - 1];
            //遍历该公司分配各个数量机器的情况，如果有任何一种情况满足了递推关系，就找到了一个答案
            for (int k = 1; k <= j; k++) {
                if (dp[i][j] == dp[i - 1][j - k] + company[k - 1]) {
                    answer[i] = k;
                    j -= k;
                    break;
                }
            }
        }
        return answer;
    }
}
